奇怪小 trick

为了浅显易懂,本文对很多简单的推导都加以说明,尽量减少跳步,尽管有些可能很好想到。所以略显冗长。

已知全集 和集合 ,且 。如何高效输出 的子集?如何高效输出 的所有子集的所有子集?

我们这里用 的二进制整数来表示一个集合,并且这些整数与集合构成双射(这里我们把集合看做有序的)。具体来说, 对应整数 ,若 的第 低位为 1,那么元素 ,否则,。比如, 对应全集 ,而 对应的 组成。

生成 的子集

如何生成?先上代码:

vector<int> generate_sub_set(int x) {
    vector<int> ret;
    for(int p=x;p;p=(p-1)&x) ret.push_back(p);
    ret.push_back(0) // 特殊处理空集
    return ret;
}

每次生成 的,而子集数量应是 个,显然复杂度 。( 指的是 二进制位中 的数量。)

关键代码就一行,很短,不是吗?

下面来证明这个的正确性(变量沿用上文, 符号表示按位与)(这个证法是我自己想的,如果有其它更好证法,欢迎在评论区提出):


命题1 一定是 的子集。

证明:我们使用了按位与 来保证,存在于 中的元素一定存在于 ),不存在于 不存在于 ),而这正是子集的定义。

命题2:枚举过程中不存在重复的集合。

证明:首先我们知道 ,因此,。所以 严格单调递减, 不会重复。又由于 的整数和集合构成双射,枚举出的集合就没有重复。

命题3:枚举过程中不存在遗漏的集合。

证明:根据命题2,由于 单调递减,等价于证明,若 是当前被枚举到的集合,则 不是 的子集。

,即 的最低的为 的二进制位位数(从低到高位,从 开始),比如 。那么 的变化就是末 位:

这个过程是根据减法的退位得到的,不必再证明了吧。

因而 的后 位显然就是 的后 位了。

因此我们可以只看后 位。设 的末 位,问题变为 内是否有 的子集。答案是否定的:任意集合 的子集 应当满足 ,又根据 ,反证,若 ,则 ,与假设矛盾,因此 。从而, 内没有 的子集。

命题3得证。


综合上述三个命题,正确性便显然了。

生成 的所有子集的所有子集

通过这个方法我们枚举的上限复杂度 并不会变,只是下限 变了。

那有什么用呢?

当生成 的所有子集的所有子集时,这个方法就有时间复杂度上的优势了。

一个暴力的想法是,直接枚举 的两个子集,判断是否是 ,复杂度

for(int x=0,ed=(1<<n);x<ed;++x)
    for(int s=0;s<ed;++s)
        if(s|x==x) cout<<s<<' ';

优化的方法也挺暴力的,就是通过刚才提到的生成子集的方法:

for(int x=0,ed=(1<<n);x<ed;++x) {
    for(int p=x;p;p=(p-1)&x) cout<<p<<' ';
    cout<<0<<' ';
}

复杂度是多少呢?

我们知道中间这个循环是 的。我们就是要计算这个:

发现顺序不重要。我们只需要统计对于每个 的个数即可。也就是:

的个数究竟是多少呢?其实就是在 位中选 位,即

那么就是:

根据二项式定理,这个式子等于

因此这个做法的复杂度是 ,优化了不少!

Upd on 2023/7/7

其实这个还有一个证明。很简单。设要求 的方案数。

对于每一个元素,都只有把它放到 ,或把它同时放到 ,或者都不放三种选择。因此有 个。